#include "stack_queue.h"
#include <vector>
#include <new>

// sq_listNode implementations
sq_listNode::sq_listNode(): next(NULL), data(0) {}

sq_listNode::sq_listNode(int nodeData, sq_listNode* succ): next(succ), data(nodeData) {}

// MyStack implementations
MyStack::MyStack(): topNode(NULL), stackSize(0) {}

MyStack::~MyStack(){
    int dummy;
    while(pop(dummy)){}
}

bool MyStack::push(const int& value){
    sq_listNode* node = new(std::nothrow) sq_listNode(value, topNode);
    if(node == NULL) return false;
    topNode = node;
    ++stackSize;
    return true;
}

bool MyStack::pop(int& item){
    if(topNode == NULL) return false;
    item = topNode->data;
    sq_listNode* toDelete = topNode;
    topNode = topNode->next;
    delete toDelete;
    --stackSize;
    return true;
}

bool MyStack::getTop(int& item){
    if(topNode == NULL) return false;
    item = topNode->data;
    return true;
}

void MyStack::printStack(){
    sq_listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            std::cout << p->data << std::endl;
        else
            std::cout << p->data << ",";

        p = p->next;
        
    }
}

// MyQueue implementations
MyQueue::MyQueue(const int& cap){
    // 使用“空一格”策略区分空/满：内部实际容量 = 传入容量 + 1
    int usable = cap > 0 ? cap : 1;
    capacity = usable + 1;
    queue = new int[capacity];
    front = 0;
    rear = 0;
}

MyQueue::~MyQueue(){
    delete [] queue;
    queue = NULL;
    capacity = 0;
    front = rear = 0;
}

bool MyQueue::isFull(){
    return ((rear + 1) % capacity) == front;
}

bool MyQueue::enQueue(const int& value){
    if(isFull()) return false;
    queue[rear] = value;
    rear = (rear + 1) % capacity;
    return true;
}

bool MyQueue::deQueue(int& item){
    if(front == rear) return false; // empty
    item = queue[front];
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int& item){
    if(front == rear) return false;
    item = queue[front];
    return true;
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            std::cout << queue[cursor] << std::endl;
        else
            std::cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

// Helpers for expression handling
static int precedence(char op){
    if(op == '+' || op == '-') return 1;
    if(op == '*' || op == '/') return 2;
    return 0;
}

static bool applyOp(int a, int b, char op, int& out){
    if(op == '+'){ out = a + b; return true; }
    if(op == '-') { out = a - b; return true; }
    if(op == '*') { out = a * b; return true; }
    if(op == '/') { if(b == 0) return false; out = a / b; return true; }
    return false;
}

bool postfixExpression(const std::string& expr, std::string& result){
    result.clear();
    MyStack opStack;
    for(size_t i = 0; i < expr.size(); ++i){
        char c = expr[i];
        if(c == ' ') continue;
        if(c >= '0' && c <= '9'){
            result.push_back(c);
        } else if(c == '('){
            if(!opStack.push((int)c)) { result = "Expression is wrong!"; return false; }
        } else if(c == ')'){
            int topVal;
            bool foundLeft = false;
            while(opStack.getTop(topVal)){
                opStack.pop(topVal);
                char op = (char)topVal;
                if(op == '('){ foundLeft = true; break; }
                if(op == '+' || op == '-' || op == '*' || op == '/') result.push_back(op);
                else { result = "Expression is wrong!"; return false; }
            }
            if(!foundLeft){ result = "Expression is wrong!"; return false; }
        } else if(c == '+' || c == '-' || c == '*' || c == '/'){
            int topVal;
            while(opStack.getTop(topVal)){
                char topOp = (char)topVal;
                if(topOp == '(') break;
                if(precedence(topOp) >= precedence(c)){
                    opStack.pop(topVal);
                    result.push_back(topOp);
                } else break;
            }
            if(!opStack.push((int)c)) { result = "Expression is wrong!"; return false; }
        } else {
            result = "Expression is wrong!";
            return false;
        }
    }
    int topVal;
    while(opStack.getTop(topVal)){
        opStack.pop(topVal);
        char op = (char)topVal;
        if(op == '(' || op == ')'){ result = "Expression is wrong!"; return false; }
        if(op == '+' || op == '-' || op == '*' || op == '/') result.push_back(op);
        else { result = "Expression is wrong!"; return false; }
    }
    return true;
}

bool expressionVal(const std::string& expr, int& result){
    result = 0;
    std::string post;
    if(!postfixExpression(expr, post)){
        return false;
    }
    MyStack valStack;
    for(size_t i = 0; i < post.size(); ++i){
        char c = post[i];
        if(c >= '0' && c <= '9'){
            if(!valStack.push(c - '0')) return false;
        } else {
            int b, a;
            if(!valStack.pop(b)) { result = 0; return false; }
            if(!valStack.pop(a)) { result = 0; return false; }
            int out;
            if(!applyOp(a, b, c, out)) { result = 0; return false; }
            if(!valStack.push(out)) { result = 0; return false; }
        }
    }
    int finalVal;
    if(!valStack.pop(finalVal)) { result = 0; return false; }
    int extra;
    if(valStack.pop(extra)) { result = 0; return false; }
    result = finalVal;
    return true;
}

void yanghui(const int& n){
    if(n <= 0) return;
    MyQueue q(n + 3);
    std::vector<int> row; row.push_back(1); row.push_back(1);
    for(int i = 0; i < n; ++i){
        for(size_t k = 0; k < row.size(); ++k){ q.enQueue(row[k]); }
        q.printQueue();
        int tmp;
        while(q.deQueue(tmp)){}
        std::vector<int> nextRow; nextRow.reserve(row.size()+1);
        nextRow.push_back(1);
        for(size_t k = 0; k + 1 < row.size(); ++k){ nextRow.push_back(row[k] + row[k+1]); }
        nextRow.push_back(1);
        row.swap(nextRow);
    }
}


